package _05_二叉树;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
 */
public class _662_二叉树最大宽度 {

    // 1.广度优先算法
    public int widthOfBinaryTree1(TreeNode root) {
        if (root == null) return 0;
        Queue<AnnotatedTreeNode> queue = new LinkedList<>();
        queue.offer(new AnnotatedTreeNode(root, 0, 0));
        int curDep = 0;
        int left = 0;
        int max = 0;
        while (!queue.isEmpty()) {
            AnnotatedTreeNode node = queue.poll();
            if (node.node != null) {
                queue.offer(new AnnotatedTreeNode(node.node.left, node.dep + 1, node.position * 2));
                queue.offer(new AnnotatedTreeNode(node.node.right, node.dep + 1, node.position * 2 + 1));
                if (curDep != node.dep) {
                    // 第一个最左边元素
                    left = node.position;
                    curDep = node.dep;
                }
                max = Math.max(max, node.position - left + 1);
            }
        }
        return max;
    }

    public static class AnnotatedTreeNode {
        TreeNode node;

        int dep;

        int position;

        public AnnotatedTreeNode(TreeNode node, int dep, int position) {
            this.node = node;
            this.dep = dep;
            this.position = position;
        }
    }

    int max;

    // 记录最左边的元素集合
    Map<Integer, Integer> map;

    // 2.深度优先算法
    public int widthOfBinaryTree2(TreeNode root) {
        if (root == null) return 0;
        map = new HashMap<>();
        dfs(root, 0, 0);
        return max;
    }

    public void dfs(TreeNode node, int dep, int position) {
        if (node == null) return;
        // 第一个最左边元素
        map.putIfAbsent(dep, position);
        max = Math.max(max, position - map.get(dep) + 1);
        dfs(node.left, dep + 1, position * 2);
        dfs(node.right, dep + 1, position * 2 + 1);
    }

}
